#include <cstdio>

int n;

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("testdata.in", "r", stdin);
  freopen("testdata.out", "w", stdout);
#endif
#ifndef LOCAL
  freopen("蓝蓝的程序.in", "r", stdin);
  freopen("蓝蓝的程序.out", "w", stdout);
#endif
#endif
  scanf("%d", &n);
  switch (n) {
    case 1:
      puts("447405405");
      break;
    case 2:
      puts("108353087");
      break;
    case 3:
      puts("584651421");
      break;
    case 4:
      puts("733427426");
      break;
    case 5:
      puts("616551897");
      break;
    case 6:
      puts("674375203");
      break;
    case 7:
      puts("499004209");
      break;
    case 8:
      puts("996450299");
      break;
    case 9:
      puts("38713062");
      break;
    case 10:
      puts("245148148");
  }
  return 0;
}